/// 表示AVL树节点方向的枚举
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AVLTreeNodeSide {
    Left = 0,
    Right = 1,
}

/// 泛型比较函数类型（替代C的void*指针）
pub type AVLTreeCompareFunc<T> = fn(left: &T, right: &T) -> std::cmp::Ordering;

/// AVL树节点结构体，使用泛型参数存储键值类型
/// 
/// 使用Rc<RefCell<T>>实现内部可变性，Weak<RefCell<T>>避免循环引用
#[derive(Debug)]
pub struct AVLTreeNode<K, V> {
    /// 子节点数组（左/右对应AVLTreeNodeSide枚举）
    pub children: [Option<std::rc::Rc<std::cell::RefCell<Self>>>; 2],
    /// 父节点指针（使用Weak避免循环引用）
    pub parent: Option<std::rc::Weak<std::cell::RefCell<Self>>>,
    /// 节点存储的键
    pub key: K,
    /// 节点存储的值
    pub value: V,
    /// 节点当前高度
    pub height: i32,
}


impl<K, V> AVLTreeNode<K, V> {
    /// 获取AVL树节点的键的不可变引用
    pub fn key(&self) -> &K {
        &self.key
    }

    /// 获取AVL树节点的值的不可变引用
    pub fn value(&self) -> &V {
        &self.value
    }

    /// 获取指定方向的子节点
    /// 
    /// # 参数
    /// - `side`: 使用AVLTreeNodeSide枚举指定子节点方向
    /// 
    /// # 返回
    /// Option包装的Rc<RefCell<AVLTreeNode<K, V>>>智能指针
    pub fn child(&self, side: AVLTreeNodeSide) -> Option<std::rc::Rc<std::cell::RefCell<Self>>> {
        self.children[side as usize].clone()
    }

    /// 获取父节点
    /// 
    /// # 返回
    /// Option包装的Rc<RefCell<AVLTreeNode<K, V>>>智能指针（Weak升级得到）
    pub fn parent(&self) -> Option<std::rc::Rc<std::cell::RefCell<Self>>> {
        self.parent.as_ref().and_then(|weak| weak.upgrade())
    }
}

/// 表示AVL树容器结构
/// 
/// 使用泛型参数K表示键类型，V表示值类型。通过智能指针管理树根节点，
/// 包含比较函数用于维护树的有序性，自动跟踪节点数量。
#[derive(Debug)]
pub struct AVLTree<K, V> {
    /// 树的根节点（使用Rc<RefCell<T>>实现内部可变性）
    pub root_node: Option<std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>>>,
    
    /// 键比较函数（使用预定义的函数指针类型）
    pub compare_func: AVLTreeCompareFunc<K>,
    
    /// 当前树中节点的总数
    pub num_nodes: usize,
}


/// 更新节点高度实现
impl<K, V> AVLTreeNode<K, V> {
    /// 计算并更新当前节点高度
    ///
    /// 根据左右子树高度最大值+1自动更新节点高度
    pub fn update_height(&mut self) {
        let left_height = self.children[AVLTreeNodeSide::Left as usize]
            .as_ref()
            .map_or(0, |n| n.borrow().height);

        let right_height = self.children[AVLTreeNodeSide::Right as usize]
            .as_ref()
            .map_or(0, |n| n.borrow().height);

        self.height = std::cmp::max(left_height, right_height) + 1;
    }

    /// 获取当前节点在父节点中的方向
    ///
    /// # 返回
    /// 当节点是父节点的左子节点时返回AVLTreeNodeSide::Left，否则返回Right
    /// 若没有父节点则panic（根据原始C代码逻辑，调用方需保证存在父节点）
    pub fn parent_side(&self, current_rc: &std::rc::Rc<std::cell::RefCell<Self>>) -> AVLTreeNodeSide {
        let parent = self.parent()
            .expect("Parent must exist when calling parent_side");
        let parent_borrow = parent.borrow();

        if let Some(left_child) = &parent_borrow.children[AVLTreeNodeSide::Left as usize] {
            if std::rc::Rc::ptr_eq(left_child, current_rc) {
                return AVLTreeNodeSide::Left;
            }
        }

        AVLTreeNodeSide::Right
    }
}

/// 树操作实现
impl<K, V> AVLTree<K, V> {
    /// 替换树中的节点
    ///
    /// 将node1替换为node2，并自动更新父节点高度
    ///
    /// # 参数
    /// - node1: 被替换的节点（Rc<RefCell<AVLTreeNode>>）
    /// - node2: 替换后的节点（Option<Rc<RefCell<AVLTreeNode>>>）
    pub fn replace_node(
        &mut self,
        node1: &std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>>,
        node2: Option<std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>>>,
    ) {
        // 获取父节点和方向
        let parent = node1.borrow().parent();

        // 设置新节点的父指针
        if let Some(node2_ref) = &node2 {
            let mut node2_borrow = node2_ref.borrow_mut();
            node2_borrow.parent = node1.borrow().parent.clone();
        }

        // 处理根节点情况
        if parent.is_none() {
            self.root_node = node2.clone();
        } else {
            let side = node1.borrow().parent_side(node1);
            let parent_rc = parent.unwrap();
            let mut parent_borrow = parent_rc.borrow_mut();
            parent_borrow.children[side as usize] = node2.clone();
            
            // 更新父节点高度
            parent_borrow.update_height();
        }
    }
}

impl<K, V> AVLTree<K, V> {
    /// 如果找到返回包含该节点的`Some(Rc<RefCell<AVLTreeNode<K, V>>>)`，否则返回`None`
    pub fn lookup_node(&self, key: &K) -> Option<std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>>> {
        let mut current_node = self.root_node.clone();
        
        while let Some(node) = current_node {
            let node_borrow = node.borrow();
            let cmp = (self.compare_func)(key, &node_borrow.key);
            
            match cmp {
                std::cmp::Ordering::Equal => return Some(node.clone()),
                std::cmp::Ordering::Less => {
                    current_node = node_borrow.children[AVLTreeNodeSide::Left as usize].clone();
                }
                std::cmp::Ordering::Greater => {
                    current_node = node_borrow.children[AVLTreeNodeSide::Right as usize].clone();
                }
            }
        }
        
        None
    }

    /// 获取AVL树当前包含的节点数量
    pub fn num_entries(&self) -> usize {
        self.num_nodes
    }

}

impl<K, V> Drop for AVLTree<K, V> {
    /// 自动释放整个AVL树及其所有节点
    /// 
    /// 通过将根节点设为None触发Rc的引用计数归零机制，
    /// 递归释放所有子节点的内存资源，节点数量计数器归零
    fn drop(&mut self) {
        self.root_node = None;
        self.num_nodes = 0;
    }
}
impl<K: Clone, V> AVLTree<K, V> {
    /// 获取当前AVL树中存储的条目数量
    ///
    /// 该函数直接访问树结构中的节点计数器，具有O(1)时间复杂度。
    /// 对应于C实现中的`avl_tree_num_entries`函数。
    ///
    /// # 返回
    /// 返回`usize`类型的节点数量，表示当前树中存储的所有键值对总数
    
    /// 包含所有键的有序Vec<K>，按中序遍历顺序排列
    pub fn to_array(&self) -> Vec<K> {
        let mut array = Vec::with_capacity(self.num_nodes);
        
        fn add_subtree<K: Clone, V>(
            node: &Option<std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>>>,
            array: &mut Vec<K>,
        ) {
            if let Some(rc_node) = node {
                let node_borrow = rc_node.borrow();
                add_subtree(&node_borrow.children[AVLTreeNodeSide::Left as usize], array);
                array.push(node_borrow.key.clone());
                add_subtree(&node_borrow.children[AVLTreeNodeSide::Right as usize], array);
            }
        }

        add_subtree(&self.root_node, &mut array);
        array
    }

    /// 创建新的AVL树实例
    ///
    /// # 参数
    /// - `compare_func`: 用于键比较的函数指针
    ///
    /// # 返回
    /// 初始化完成的AVLTree实例，包含空根节点和零节点计数
    /// 创建新的AVL树实例
    ///
    /// # 参数
    /// - `compare_func`: 用于键比较的函数指针
    ///
    /// # 返回
    /// 初始化完成的AVLTree实例，包含空根节点和零节点计数
    pub fn new(compare_func: AVLTreeCompareFunc<K>) -> Self {
        AVLTree {
            root_node: None,
            compare_func,
            num_nodes: 0,
        }
    }
    /// # 参数
    /// - `key`: 要插入的键，类型为K
    /// - `value`: 要插入的值，类型为V
    pub fn insert(&mut self, key: K, value: V) -> Option<std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>>> {
        let mut parent = None;
        let mut current = self.root_node.clone();
        
        while let Some(node) = current {
            let node_borrow = node.borrow();
            parent = Some(node.clone());
            
            match (self.compare_func)(&key, &node_borrow.key) {
                std::cmp::Ordering::Less => {
                    current = node_borrow.children[AVLTreeNodeSide::Left as usize].clone();
                }
                _ => {
                    current = node_borrow.children[AVLTreeNodeSide::Right as usize].clone();
                }
            }
        }

        // 创建新节点
        let new_node = std::rc::Rc::new(std::cell::RefCell::new(AVLTreeNode {
            children: [None, None],
            parent: parent.as_ref().map(|p| std::rc::Rc::downgrade(p)),
            key,
            value,
            height: 1,
        }));

        // 插入到父节点
        if let Some(ref parent_node) = parent {
            let mut parent_borrow = parent_node.borrow_mut();
            let side = match (self.compare_func)(&new_node.borrow().key, &parent_borrow.key) {
                std::cmp::Ordering::Less => AVLTreeNodeSide::Left,
                _ => AVLTreeNodeSide::Right,
            };
            parent_borrow.children[side as usize] = Some(new_node.clone());
        } else {
            self.root_node = Some(new_node.clone());
        }

        // 平衡树结构
        if let Some(ref parent_node) = parent {
            self.balance_to_root(parent_node.clone());
        }

        self.num_nodes += 1;
        Some(new_node)
    }

    /// 执行AVL树旋转操作
    pub fn rotate(
        &mut self,
        node: std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>>,
        direction: AVLTreeNodeSide,
    ) -> std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>> {
        let new_root = {
            let node_borrow = node.borrow();
            node_borrow.children[1 - direction as usize].clone().expect("Rotation requires valid child")
        };

        self.replace_node(&node, Some(new_root.clone()));

        {
            let mut node_mut = node.borrow_mut();
            let mut new_root_mut = new_root.borrow_mut();
            
            node_mut.children[1 - direction as usize] = new_root_mut.children[direction as usize].clone();
            new_root_mut.children[direction as usize] = Some(node.clone());

            node_mut.parent = Some(std::rc::Rc::downgrade(&new_root));

            if let Some(child) = &node_mut.children[1 - direction as usize] {
                child.borrow_mut().parent = Some(std::rc::Rc::downgrade(&node));
            }
        }

        node.borrow_mut().update_height();
        new_root.borrow_mut().update_height();

        new_root
    }

    /// 从指定节点向上平衡至根节点
    pub fn balance_to_root(&mut self, node: std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>>) {
        let mut rover = Some(node);
        while let Some(current) = rover.take() {
            let parent = current.borrow().parent();
            let balanced = self.balance_node(current);
            rover = parent;
            if rover.is_none() {
                self.root_node = Some(balanced);
            }
        }
    }

    /// 平衡指定节点并返回新的根节点
    pub fn balance_node(
        &mut self,
        node: std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>>,
    ) -> std::rc::Rc<std::cell::RefCell<AVLTreeNode<K, V>>> {
        let left_height = node.borrow().children[AVLTreeNodeSide::Left as usize]
            .as_ref()
            .map_or(0, |n| n.borrow().height);
        let right_height = node.borrow().children[AVLTreeNodeSide::Right as usize]
            .as_ref()
            .map_or(0, |n| n.borrow().height);
        let diff = left_height - right_height;

        let mut current_node = node;

        if diff >= 2 {
            let left_child = current_node.borrow().children[AVLTreeNodeSide::Left as usize]
                .clone().expect("Left child must exist");

            let (left_left, left_right) = {
                let child = left_child.borrow();
                (
                    child.children[AVLTreeNodeSide::Left as usize].as_ref().map_or(0, |n| n.borrow().height),
                    child.children[AVLTreeNodeSide::Right as usize].as_ref().map_or(0, |n| n.borrow().height)
                )
            };

            if left_left < left_right {
                self.rotate(left_child.clone(), AVLTreeNodeSide::Left);
            }

            current_node = self.rotate(current_node, AVLTreeNodeSide::Right);
        } else if diff <= -2 {
            let right_child = current_node.borrow().children[AVLTreeNodeSide::Right as usize]
                .clone().expect("Right child must exist");

            let (right_left, right_right) = {
                let child = right_child.borrow();
                (
                    child.children[AVLTreeNodeSide::Left as usize].as_ref().map_or(0, |n| n.borrow().height),
                    child.children[AVLTreeNodeSide::Right as usize].as_ref().map_or(0, |n| n.borrow().height)
                )
            };

            if right_right < right_left {
                self.rotate(right_child.clone(), AVLTreeNodeSide::Right);
            }

            current_node = self.rotate(current_node, AVLTreeNodeSide::Left);
        }

        current_node.borrow_mut().update_height();
        current_node
    }
}